package com.leetcode.binary_search;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/9/24 16:01
 */
public class ShipWithinDays_1011 {

    public int shipWithinDays(int[] weights, int D) {
        // 这一道题的最大值需要根据和来取 -- 区别于香蕉
        int i = 1, j = Arrays.stream(weights).sum();
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (isSatisfied(weights, mid, D)) {
                j = mid;
            } else {
                i = mid + 1;
            }
        }
        return i;
    }

    private boolean isSatisfied(int[] weights, int mid, int d) {
        int sum = 0;
        for (int weight : weights) {
            // 当货物重量超过最大载重，直接返回false
            if (weight > mid)
                return false;
            sum += weight;
            if (sum >= mid) {
                d--;
                // 如果恰好相等，则返回0（即运输这次货物），如果不等，那么这次不运，返回weight
                sum = sum == mid ? 0 : weight;
            }
        }
        return d > 0;
    }

}
